import java.util.Map;

// 返回两个无环链表相交的第一个节点
// 测试链接 : https://leetcode.cn/problems/intersection-of-two-linked-lists/
public class IntersectionOfTwoLinkedLists {
    public static class ListNode {
        public int val;
        public ListNode next;
    }

    public static ListNode getIntersectionNode(ListNode h1, ListNode h2) {
        if(h1 == null || h2 == null){ //如果其中一个结点为空则没有交点
            return null;
        }
        ListNode a = h1;
        ListNode b = h2;
        int diff = 0; //默认a链表长度更长，记录a链表的长度

        while (a != null) {
            diff++;
            a = a.next;
        }

        while (b != null) {
            diff--;   //记录两条链表的相差的长度
            b = b.next;
        }

        a = h1;
        b = h2;

        if(diff < 0) {  //此时表示b链表更长,调整a,b指向
            a = h2;
            b = h1;
        }
        diff = Math.abs(diff);
        while (diff-- !=0) {
            a = a.next;      //先让a(长链表走差值的长度)
        }

        while(a != null && b != null) {
            if(a == b) {   //找到相交位置点
                return a;
            }
            a = a.next;
            b = b.next;
        }

        return null;
    }
}
